package tree.leetcode_98_medium;

public class BestSolution {
    /**
     * 验证二叉搜索树：二叉搜索树的中序遍历结果是一个递增的序列，使用一个变量记录当前节点的前一个节点，如果前一个节点值 >= 当前节点，则不是BST
     * @param root  给定一棵树的根节点
     * @return      返回是否是二叉搜索树
     */
    public boolean isBST(TreeNode root){
        if(root == null){
            return true;
        }
        TreeNode pre = null;
        while(root != null){
            TreeNode mostLeft = root.left;
            if(mostLeft != null){
                while(mostLeft.right != null && mostLeft.right != root){
                    mostLeft = mostLeft.right;
                }
                if(mostLeft.right == null){
                    mostLeft.right = root;
                    root = root.left;
                }else{
                    //这时是第二次回到节点，
                    if(pre != null && pre.val >= root.val){
                        return false;
                    }
                    pre = root;
                    mostLeft.right = null;
                    root = root.right;
                }
            }else{
                if(pre != null && pre.val >= root.val){
                    return false;
                }
                pre = root;
                root = root.right;
            }
        }
        return true;
    }
}
